Grokking Meta Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Meta Easy Problems
Toeplitz Matrix (easy)
Solution: Toeplitz Matrix
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Island Perimeter (easy)
Solution: Island Perimeter
Moving Average from Data Stream (easy)
Solution: Moving Average from Data Stream
Move Zeroes (easy)
Solution: Move Zeroes
Missing Ranges (easy)
Solution: Missing Ranges
Palindrome Permutation (easy)
Solution: Palindrome Permutation
Rank Transform of an Array (easy)
Solution: Rank Transform of an Array
Diagonal Traverse (medium)
Solution: Diagonal Traverse
Shortest Path in Binary Matrix (medium)
Solution: Shortest Path in Binary Matrix
Maximum Swap (medium)
Solution: Maximum Swap
Custom Sort String (medium)
Solution: Custom Sort String
Binary Tree Vertical Order Traversal (medium)
Solution: Binary Tree Vertical Order Traversal
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Basic Calculator II (medium)
Solution: Basic Calculator II
Nested List Weight Sum (medium)
Solution: Nested List Weight Sum
Dot Product of Two Sparse Vectors (medium)
Solution: Dot Product of Two Sparse Vectors
Max Consecutive Ones III (medium)
Solution: Max Consecutive Ones III
Subarray Sum Equals K (medium)
Solution: Subarray Sum Equals K
Next Permutation (medium)
Solution: Next Permutation
Simplify Path (medium)
Solution: Simplify Path
Lowest Common Ancestor of a Binary Search Tree (medium)
Solution: Lowest Common Ancestor of a Binary Search Tree
'K' Closest Points to the Origin (medium)
Solution: 'K' Closest Points to the Origin
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Merge Intervals (medium)
Solution: Merge Intervals
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Number of Islands (medium)
Solution: Number of Islands
Clone Graph (medium)
Solution: Clone Graph
Missing Element in Sorted Array (medium)
Solution: Missing Element in Sorted Array
Number of Substrings Containing All Three Characters (medium)
Solution: Number of Substrings Containing All Three Characters
Capacity To Ship Packages Within D Days (medium)
Solution: Capacity To Ship Packages Within D Days
Count and Say (medium)
Solution: Count and Say
Contiguous Array (medium)
Solution: Contiguous Array
Sliding Window Median (hard)
Solution: Sliding Window Median
Alien Dictionary (hard)
Solution: Alien Dictionary
Minimum Window Substring (hard)
Solution: Minimum Window Substring
Best Meeting Point (hard)
Solution: Best Meeting Point
Maximum Sum of 3 Non-Overlapping Subarrays (hard)
Solution: Maximum Sum of 3 Non-Overlapping Subarrays
Making A Large Island (hard)
Solution: Making A Large Island
Basic Calculator (Hard)
Solution: Basic Calculator
Serialize and Deserialize Binary Tree (hard)
Solution: Serialize and Deserialize Binary Tree
Longest Increasing Path in a Matrix (hard)
Solution: Longest Increasing Path in a Matrix
Valid Palindrome III (hard)
Solution: Valid Palindrome III
Solution: Toeplitz Matrix

Problem Statement

Given an m x n matrix, determine if the given matrix is a Toeplitz matrix.

A Toeplitz matrix is one in which every diagonal from top-left to bottom-right has the same elements.

In other words, the matrix should have the property that each element is equal to the element diagonally down to its right.

Example 1:

  • Input:
[[1,2,3],
 [4,1,2],
 [5,4,1]]
  • Expected Output: true
  • Justification: All diagonals have the same elements. Diagonals of the above matrix are [5], [4, 4], [1, 1, 1], [2, 2], and [3].

Example 2:

  • Input:
[[1,2],
 [3,4]]
  • Expected Output: false
  • Justification: The diagonal are [3], [1, 4], and [2]. A diagonal [1, 2] doesn't have the same elements.

Example 3:

  • Input:
[[7,7,7],
 [7,7,7],
 [7,7,7]]
  • Expected Output: true
  • Justification: Each diagonal, although containing the same repeated element (7), satisfies the condition of a Toeplitz matrix.

Solution

To solve this problem, we will iterate through the elements of the matrix, checking if each element (except those in the last row and last column) matches with its diagonal successor. This approach works because a Toeplitz matrix is defined by the consistency of elements along its diagonals. By verifying this condition, we can ensure whether the matrix adheres to the Toeplitz criteria.

Step-by-step Algorithm

  • Iterate over each row of the matrix, except the last row.
    • For each row, iterate over each column, except the last column.
      • Check if the current element is equal to the element diagonally down to its right.
      • If any such pair of elements is not equal, return false immediately.
  • If the entire matrix is iterated without finding any mismatch, return true.

Algorithm Walkthrough

Using Example 1: matrix =

[[1,2,3],
 [4,1,2],
 [5,4,1]]
  • Start with the first element (1) at matrix[0][0]. It matches with its diagonal successor (1) at matrix[1][1]. Continue.
  • Move to the second element (2) in the first row at matrix[0][1]. It matches with its diagonal successor (2) at matrix[1][2]. Continue.
  • Skip the last element (3) in the first row as it has no diagonal successor.
  • Move to the first element (4) in the second row. It matches with its diagonal successor (4). Continue.
  • Next, Move to the second element (1) in the second row. It matches with its diagonal successor (1). Continue.
  • Skip the last element (2) in the second row.
  • Since we've reached the last row, we conclude that the matrix is a Toeplitz matrix.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

  • Time Complexity: , where m is the number of rows and n is the number of columns in the matrix. Each element is checked once.
  • Space Complexity: , as no extra space is used besides a few variables for iteration.
Toeplitz Matrix (easy)
Remove All Adjacent Duplicates In String (easy)
Mark as Completed

On this page

Problem Statement

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis